package JZ_Offer.algorithm.other.基础数学;

/**
 * 整数中1出现的次数（从1到n整数中1出现的次数）
 * <p>
 * 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
 * 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。
 * ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
 *
 * @Author piper
 * @Date 2020/1/7 10:58 上午
 */
public class JZ43_整数中1出现的次数 {

    // 双指针 求每一个数字1的个数 对于个位 对10取余 可以判断是否为1 再将原数除10替换 以此类推 求出十百千位
    private static int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = n; i > 0; i--) {
            // 分别判断数字各位是否为1
            // 对10取余 得到最后一位数字
            // 除10 去掉最后一位数字
            for (int j = i; j > 0; j /= 10) {
                if (j % 10 == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 从 1 至 10，在它们的个位数中，任意的 x 都出现了 1 次
     * 从 1 至 100，在它们的十位数中，任意的 x 都出现了 10 次
     * 从1至1000，在它们的百位数中，任意的x都出现了100次
     * 依次类推，从 1 至 10i，在它们的左数第二位(右数第 i 位)
     * 任意的 x 都出现了 (10i-1)次。这个规律很容易验证，这里不再多做说明
     */
    private static int NumberOf1Between1AndN_Solution1(int n) {
        if (n < 1) return 0;
        if (n < 9) return 1;
        int count = 0;

        for (int i = 1; i <= n; i *= 10) {
            int k = n / i;
            int high = k / 10;
            count += high * i;
            // 可能会有不完整部分
            int cur = k % 10;
            if (cur > 1)
                count += i;
            else if (cur == 1)
                count += n - k * i + 1;
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(NumberOf1Between1AndN_Solution1(20));
    }
}
